package problem229_Majority_Element_II;

import java.util.LinkedList;
import java.util.List;

public class Solution {
	public List<Integer> majorityElement(int[] nums) {
		List<Integer> result=new LinkedList<>();
		if(nums.length==0)
			return result;
        int candidate1=nums[0],candidate2=nums[0],count1=0,count2=0;
        for(int n:nums){
        	if(n==candidate1){
        		count1++;
        	}else if(n==candidate2){
        		count2++;
        	}else if(count1==0){
        		candidate1=n;
        		count1++;
        	}else if(count2==0){
        		candidate2=n;
        		count2++;
        	}else{
        		count1--;
        		count2--;
        	}
        }
        count1=0;count2=0;
        for(int n:nums){
        	if(n==candidate1)
        		count1++;
        	else if(n==candidate2){
        		count2++;
        	}
        }
        if(count1>nums.length/3)
        	result.add(candidate1);
        if(count2>nums.length/3&&candidate2!=candidate1)
        	result.add(candidate2);
        return result;
    }
}
